
// 找到子数组使得之和为k,记录次数
// 其实就是找到一个区间[i, j]使得这个区间的数字之和为k
// 那么就可以枚举每一个区间
// 1、暴力法
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// O(N*2)超时
var subarraySum = function(nums, k) {
    let count = 0
    for(let i = 0; i < nums.length; i++) {
        let sum = 0
        for(let j = i; j < nums.length; j++) {
            // 这里省去了每次重新求[i, j]之间的和
            // 因为求[0, 1]的时候[0, 0]已经计算过了，所以不需要重复求，每次求的时候记录即可
            sum += nums[j]
            if(sum == k) count++
        }
    }
    return count
};
// 优化假设一个前缀和prefixSum[x]表示区间[0, x]之间的和
// 我们要求的是[i, j]区间和为k的个数
// sum[i, j] = prefixSum[j] - prefixSum[i - 1]
// 其实也就是求满足条件i, j组合的个数

// 两数之和，变为两前缀和之差
var subarraySum = function(nums, k) {
    const map = {
        0: 1
    }
    let count = 0
    let prefixSum = 0
    for(let i = 0; i < nums.length; i++) {
        prefixSum += nums[i]
        if(map[prefixSum - k]) {
            count += map[prefixSum - k]
        }
        if(map[prefixSum]) {
            map[prefixSum]++
        } else {
            map[prefixSum] = 1
        }
    }
    return count
};